﻿#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <memory>
#include <functional>

using namespace std;

// 
// 以下是前缀和专题，运用前缀和思想有以下注意事项
// 前缀和模版分为一维模版和二维模版，提前分别求出一维和二维数组的和
// 求和运用的思想是动态规划的思想
// 
// 第26题 #########################################################
// 
//DP34 【模板】前缀和
//描述
//给定一个长度为n的数组
//a1,a2,....ana1​, a2​, ....an.
//接下来有q次查询, 每次查询有两个参数l, r. 对于每个询问, 
//请输出al+al+1+....+aral​+ al + 1​+ .... + ar​
//输入描述：第一行包含两个整数n和q.	第二行包含n个整数, 
//表示a1,a2,....ana1​, a2​, ....an.
//接下来q行, 每行包含两个整数l和r.  1≤n,q≤10^5,1≤n, q≤10^5,
//−109≤a[i]≤10^9, −10^9≤a[i]≤10^9, 1≤l≤r≤n, 1≤l≤r≤n
//输出描述：
//输出q行, 每行代表一次查询的结果.
//示例1
//输入：3 2
//	    1 2 4
//	    1 2
//	    2 3
//输出：
//      3
//      6
//
// 牛客网上的题目很多是多次输入
// 多次输入会带来更多效率方面的考虑
// 对于这个题目来说，提前将前缀和数组进行加载，
// 可以再每次查询时都通过前缀和数组元素的相减得到结果
// 
//
//int main() {
//    int numofarr;
//    int numoffind;
//    cin >> numofarr >> numoffind;
//    vector<long long int> arr(numofarr + 1);
//    for (int i = 1; i < numofarr + 1; i++)
//    {
//        cin >> arr[i];
//    }
//
//    vector<int> dp(numofarr + 1, 0);
//    for (int i = 1; i < numofarr + 1; i++)
//    {
//        dp[i] = dp[i - 1] + arr[i];
//    }
//
//    while (numoffind--)
//    {
//        int l;
//        int r;
//        cin >> l >> r;
//        long long int ret = dp[r] - dp[l - 1];
//        cout << ret;
//    }
//
//    return 0;
//}
// 
// 第27题 #########################################################
//
// 【模板】二维前缀和
// 给你一个 n 行 m 列的矩阵 A ，下标从1开始。
// 接下来有 q 次查询，每次查询输入 4 个参数 x1, y1, x2, y2
// 请输出以(x1, y1) 为左上角, (x2, y2) 为右下角的子矩阵的和，
// 输入描述：
// 第一行包含三个整数n, m, q.
// 接下来n行，每行m个整数，代表矩阵的元素
// 接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数
// 1 <= n, m <= 1000 1 <= q <= 10^5
// -10^9 <= a[i][i] <= 10^9, 1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= m
// 输出描述：
// 输出q行，每行表示查询结果。
//
// 示例1： 
// 输入：
//		 3 4 3
//		 1 2 3 4
//		 3 2 1 0
//		 1 5 7 8
//		 1 1 2 2
//		 1 1 3 3
//		 1 2 3 4
// 输出：
//		 8
//		 25
//		 32
//
//int main() 
//{
//	int n;
//	int m;
//	int q;
//	cin >> n >> m >> q;
//	vector<vector<long long int>> matrix(n + 1, vector<long long int>(m + 1, 0));
//	for (int i = 1; i < n + 1; i++)
//	{
//		for (int j = 1; j < m + 1; j++)
//		{
//			cin >> matrix[i][j];
//		}
//	}
//
//	//  1   2   3   0
//	// -1   2  -3  -4
//	//  1   2  -2 -19
//	// -1  20   2 -99
//
//	vector<vector<long long int>> dp(n + 1, vector<long long int>(m + 1, 0));
//	for (int i = 1; i < n + 1; i++)
//	{
//		for (int j = 1; j < m + 1; j++)
//		{
//			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j];
//		}
//	}
//
//	while (q--)
//	{
//		int x1, x2, y1, y2;
//		cin >> x1 >> y1 >> x2 >> y2;
//		cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
//	}
//
//	return 0;
//}
// 
// 第28题 #########################################################
//
// 724. 寻找数组的中心下标
// 
// 给你一个整数数组 nums ，请计算数组的 中心下标 。
//数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
//如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。
//这一点对于中心下标位于数组最右端同样适用。
//如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 - 1 。
//示例 1：	输入：nums = [1, 7, 3, 6, 5, 6]		输出：3
//解释：中心下标是 3 。
//左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
//右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
//
class Solution1 {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        vector<int>f(n + 1, 0);
        vector<int>g(n + 1, 0);
        for (auto& num : nums)
        {
            sum += num;
        }

        for (int i = 1; i < n; i++)
        {
            f[i] = f[i - 1] + nums[i - 1];
            g[i] = sum - f[i];
        }

        for (int i = 0; i < n; i++)
        {
            if (f[i - 1] == g[i])
            {
                return i - 1;
            }
        }
        return -1;
    }
};

int main()
{
    return 0;
}